//
//  ProblemMS1617.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/12.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 16.17. 连续数列
 给定一个整数数组，找出总和最大的连续数列，并返回总和。

 示例：
     输入： [-2,1,-3,4,-1,2,1,-5,4]
     输出： 6
     解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
 进阶：
    如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 */
@objcMembers class ProblemMS1617: NSObject {
    func solution() {
        print(maxSubArrayFZ([-2,1,-3,4,-1,2,1,-5,4]))
    }
    
    /*
     动态规划：
     1: 创建一个数组dp[len]
     2: dp[i]表示以i为结尾的字数组最大的和
     3: 对于位置i，必须给以i为结尾，所以：要不自己组成一个队列，要不和前面的队列合并
     */
    func maxSubArray(_ nums: [Int]) -> Int {
        var dp:[Int] = Array(repeating: Int.min, count: nums.count)
        dp[0] = nums[0]
        for i in 1..<nums.count {
            dp[i] = max(nums[i], dp[i-1]+nums[i])
        }
        print(dp)
        return dp.max() ?? 0
    }
    
    /*
     动态规划：优化，
     省略dp数组，创建一个数maxValue,每次记录最大值
     2: dp[i]表示以i为结尾的字数组最大的和
     
     */
    func maxSubArrayClear(_ nums: [Int]) -> Int {
        var maxValue: Int = nums[0]
        var lastDP = nums[0]
        for i in 1..<nums.count {
            lastDP = max(nums[i], lastDP+nums[i])
            maxValue = max(lastDP, maxValue)
        }
        return maxValue
    }
    
    /*
     分治算法：来自官方题解
     将问题分解成小段后，再合并
     分：
     1: 计算[l, r]这个区间，那么我们将区间分成[l, mid)和[mid, r]
     2: 在[l, r]这个区间，我们计算一下这个区间的4个值,
        lSum: 以l为开始的最大和
        rSum: 以r为结尾的最大和
        mSum: 区间中的最大子数组和（就是我们要求的和）
        aSum: 区间所有值的总和
     合：
     3: 我们分别求这4个值，根据[l, mid)和[mid, r]他们的4个值来求出
        lSum：他有2种情况：1:左区间[l, mid)的lSum， 2:左区间[l, mid)的aSum + 右区间[mid, r]的lSum
        rSum：他有2种情况：1:右区间[mid, r]的rSum， 2:右区间[mid, r]的aSum + 左区间[mid, r]的rSum
        aSum: 左aSum + 右aSum
        mSum: 他有3种情况: 1: 就是左的mSum, 2: 就是右的mSum，3:如果正好夸2个区间，那么就是 左rSum+右lSum
     4: 特例：l==r：就一个值，那么这4个都是num[l]
     */
    
    struct qsum {
        var lSum: Int = 0
        var rSum: Int = 0
        var mSum: Int = 0
        var aSum: Int = 0
        
        init(l: Int, r: Int, m: Int, a: Int) {
            lSum = l
            rSum = r
            mSum = m
            aSum = a
        }
    }
    
    func maxSubArrayFZ(_ nums: [Int]) -> Int {
        return getQSum(nums, 0, nums.count-1).mSum
    }
    
    func getQSum(_ nums: [Int], _ l: Int, _ r: Int) -> qsum {
        if l == r {     // 特例
            return qsum(l: nums[l], r: nums[l], m: nums[l], a: nums[l])
        }
        let mid = l + (r - l) >> 1
        let lQSum = getQSum(nums, l, mid)
        let rQSum = getQSum(nums, mid+1, r)
        
        return qsum(l: max(lQSum.lSum, lQSum.aSum + rQSum.lSum), r: max(rQSum.rSum, rQSum.aSum + lQSum.rSum), m: max(lQSum.mSum, rQSum.mSum, lQSum.rSum+rQSum.lSum), a: lQSum.aSum+rQSum.aSum)
    }
}
